Wavelength Division Multiplexing (WDM) is a type of multiplexing developed for use on an optical fiber. WDM modulates each of several data streams onto a different part of the light spectrum. That is, WDM transmits each data stream at a different optical wavelength.
WDM has established itself as an inexpensive and reliable mechanism for transporting information bits in metro and long-haul networks. WDM networks also provide the underlying transport for the growing Internet data traffic that has more variance and, therefore, creates greater network churn. As this traffic continues to grow and capital budgets fail to keep up (or, even shrink), service providers are increasingly seeking tools that enable them to extract higher utilization from their existing infrastructure.
Of course, the desire to extract higher utilization from a network is not restricted to WDM networks. Other types of ring networks benefit from improved network utilization techniques. For instance, improved network utilization techniques would be equally beneficial in ring networks based on synchronous optical network (SONET) or synchronous digital hierarchy (SDH) standards, particularly when all circuits are of uniform granularity.
Traditional optimization tools solve the problem of improving network utilization by providing a optimal layout, comprising a routing and wavelength assignment (RWA) plan, for a given set of demands. A demand is a request for a wavelength between two nodes in the network. A circuit is provisioned to satisfy a demand and is characterized by a route and assigned wavelength number. The terms “demand” and “circuit,” as used herein, may be used interchangeably.
While such tools are valuable during network planning to design the cheapest WDM network that can support a projected set of demands, they are of little use in optimizing an operational network, as implementing the recommended RWA requires service disruption.
By way of example, FIG. 1A represents the initial routing and wavelength assignment plan for the set of circuits on a WDM ring of eight nodes (x-axis) and six wavelengths (y-axis). It is assumed that the ring is cut at node 1, for illustration purposes. It is also assumed that demand D is routed along path 5→4→3→2→1→8 and occupies wavelength 2 on the ring. FIG. 1B shows the optimum layout generated by an optimization algorithm such as is disclosed in T. J. Carpenter et al., “Demand Routing and Slotting on Ring Networks;” DIMACS Technical Report, Tech Rep., January 1997, the disclosure of which is incorporated by reference herein. In order to attain the optimal state without service disruption, the network operator requires not only the final RWA as illustrated in FIG. 1B, but more importantly, a sequence of disruption free circuit moves to transition from existing state to optimal state.
However, unlike network design, online or real-time optimization is performed on networks that carry live traffic, so it should be “hitless,” i.e., cause no service disruption. Thus, in addition to optimizing the layout of circuits, it is equally desirable to determine a hitless re-routing sequence to migrate the ring from the original to new optimal layout. Otherwise, this effort has little use in practice.
In traditional WDM rings comprising optical add-drop multiplexer (OADM) elements, re-routing traffic was often a very cumbersome task and in many cases, impossible to achieve without disruption. However, newer network elements called Reconfigurable OADM or ROADM elements (see, e.g., A. M. Saleh et al., “Architectural Principles of Optical Regional and Metropolitan Access Networks,” Journal of Lightwave Technology, vol. 17, December 1999; and M. D. Feuer et al., “Routing Power: A Metric for Reconfigurable Wavelength Add/Drops,” OFC 2002, the disclosures of which are incorporated by reference herein), equipped with optical cross-connects, support a Bridge-n-Roll functionality similar to Automatic Protection Switching (APS). This enables circuits to be first replicated on to the new route/wavelength (bridged), and then switched or rolled over seamlessly with no service hit. This process is akin to make-before-break in Multi Protocol Label Switching (MPLS) networks. ROADM are typically deployed as modular elements with multiple wavelength bands. In such a scenario, a circuit can only be Bridge-n-Rolled to another wavelength in the same band.
On a WDM ring of ROADMs equipped with Bridge-n-Roll functionality, a circuit can be rerouted in three ways: (a) flipping the route from clockwise to counter-clockwise (or vice versa); (b) routing the circuit on a different wavelength; or (c) doing both a and b. For example, one such circuit rerouting sequence to transition from the layout in FIG. 1A to the layout in FIG. 1B is shown in FIG. 2. Principles of the invention address the problem of finding such a sequence, given initial and final RWA layouts.
Thus, online ring optimization requires addressing two critical, yet distinct problems: (1) the routing and wavelength assignment (RWA) for ring topology; and (2) the circuit migration problem.
There is vast body of research on the RWA problem on rings, since it is a variant of the well-addressed Demand Routing and Slotting Problem (DRSP). The ring sizing and the ring loading are specific examples of the DRSP and these are all proven to be NP-hard. Good approximations to these problems do exist. In fact, ring loading can be optimally solved for the case when all demands are of same granularity.
However, there is very little previous work on the circuit migration problem. S. Acharya et al., “Hitless Network Engineering of SONET Rings,” Globecom, 2003, the disclosure of which is incorporated by reference herein, addressed online ring optimization problem in an integrated fashion. They found a sub-optimal solution using a cost-based heuristic along with a transition sequence. Although it performs reasonably well in practice, there is no guarantee on quality of solution.
It is therefore apparent that improved techniques are needed for dealing with the issue of providing a circuit migration sequence from a given layout to a known optimal layout obtained using any known optimal layout algorithms.